\section{Eternity II}
Eternity II es un juego de mesa, creado por Christopher Monckton, que consiste
en un rompecabezas del tipo \textit{Edge-Matching} de 256 piezas cuadradas las cuales poseen dibujos geométricos coloreados 
que deben coincidir en un tablero de $16\times16$.\\

Cada pieza tiene sus bordes marcados con diferentes combinaciones de forma/color y los mismos deben 
coincidir con los bordes de sus fichas vecinas. Se utiliza sólo una cara de las piezas, 
por lo tanto cada ficha puede ser utilizada en solo 4 orientaciones. 
Existen 22 combinaciones de forma/color sin contar los bordes que se consideran siempre planos de color gris.
Como ayuda para la resolución, el juego original indica una ficha inicial que debe ubicarse cerca del 
centro del tablero.\\
 
Al momento de su lanzamiento existía una recompensa de 2 millones de dólares para el primero que 
encontrase una solución, sin embargo hasta el día de la fecha no se conoce
 una solución completa.\\


\begin{figure}[ht!]
\centering
\includegraphics[width=90mm]{imagenes/eternity2.jpg}
\caption{Juego de mesa Eternity II}
\label{overflow}
\end{figure}


\subsection{Historia}
En el año 1999 Christopher Monckton lanzó la primer versión de este juego,
denominado Eternity, con una recompensa de 1 millón de libras británicas para
aquel que presentase una solución exacta antes de Septiembre del 2003. 
A diferencia de su segunda versión, Eternity era un rompecabezas del tipo \textit{Tilling} que consistía 
en llenar un dodecágono regular con 209 piezas del mismo color pero de formas
i\-rre\-gu\-la\-res.\\

El rompecabezas fue resuelto en el año 2000 (dos años antes de lo que Monckton estimaba) por dos matemáticos
de Cambridge, Alex Selby y Oliver Riordan que explotaron ciertas debilidades en el diseño del rompecabezas
mediante ingeniosos cálculos probabilísticos y un algoritmo tipo Breadth-First
Search (BFS) \cite{Selby}.
El premio se pagó en parte con la venta de una propiedad de Monkton y con una aseguradora.\\

En el año 2007 Monckton, esta vez con colaboración de Selby y Riordan, lanzó la segunda versión del juego llamado 
Eternity II con un premio de 2 millones de dólares para quien resolviera el rompecabezas antes de Febrero de 2011. 
El diseño de este rompecabezas tuvo como objetivo mejorar las debilidades de la primer versión dando como resultado 
un rompecabezas que al parecer cuenta con un número reducido posibles soluciones. 
Según palabras de Monckton en una nota con la revista The Times:

\begin{quotation}
\em ``Nuestros cálculos indican que si se utilizase la computadora mas poderosa del mundo y se dejase correr a partir de ahora
hasta el final previsto del universo no podría encontrarse con una de las soluciones''.
\end{quotation}

En el año 2008 Louis Verhaard recibió un premio de diez mil dólares por presentar una solución parcial
con 467 coincidencias de un total de 480, pero aún al día de la fecha, se
desconoce una solución completa.

\subsection{Descripción del problema}
Para tener una noción de la complejidad que puede llevar la resolución del
rompecabezas, contamos las combinaciones que pueden formarse con el mismo. Las 4 piezas de las esquinas (dos bordes grises) pueden ser
ubicadas de $4!$ formas posibles, las 56 piezas de los bordes (un borde gris) pueden ser ubicadas de $56!$
formas posibles y las 196 piezas interiores pueden ser ubicadas de $196! * 4^{196}$  formas posibles teniendo 
en cuenta que estas últimas pueden ser rotadas. Esto da como resultado un total
aproximado de:\\

\begin{equation*}
4! + 56! + 196! * 4^{196} \approx 5.12 * 10^{483}\\
\end{equation*}  

Cada una de estas combinaciones es una posible solución.\\

Erik y Martin Demaine \cite{Demaine} demostraron que existe una equivalencia
directa entre rompecabezas del tipo \textit{Jigsaw}, \textit{Edge Matching} y \textit{Polinomio Packing} y que
la resolución de todos ellos es NP-completo. A fin de que el
lector comprenda el significado de esto último en el contexto de nuestro trabajo, podemos decir que un problema NP-completo implica, entre otras cosas, que no 
se conoce a la fecha un algoritmo que lo resuelva de forma eficiente (en un
tiempo polinomial respecto del tamaño de la entrada) y, más aun, tal
vez ese algoritmo nunca exista \cite{Garey}.\\

El problema es comunmente modelado como un problema CSP \textit{(Constraint
Sa\-tis\-fac\-tion Problem)} \cite{Sally}. CSPs son problemas matemáticos que se
definen mediante una serie de restricciones que deben ser satisfechas asignando valores a las
variables presentes en las restricciones. De cierta forma, son una
generalización de SAT \textit{(Boolean Satisfiabity Problem)}, donde en lugar de buscar
una asignación de valores booleanos que satisfagan una fórmula se busca una
asignación a variables multivaluadas que satisfagan todas las restricciones.
Los valores posibles para cada variable dependen del problema y pueden pertenecer a
dominios distintos. Formalmente se define un problema CSP con una tupla de la
siguiente manera: \\

\begin{equation*}
\langle \{ x_1, x_2, \ldots , x_n\} , \{ d_1, d_2, \ldots , d_n\}, \{ c_1, c_2,
\ldots , c_m\} \rangle
\end{equation*}

\noindent donde $x_1, x_2, \ldots , x_n$ son las variables, $d_1, d_2, \ldots ,
d_n$ son los dominios de cada una de las variables, es decir, los valores que
pueden tomar las mismas y $c_1, c_2, \ldots , c_m$ son las restricciones.\\

Debido al gran espacio de búsqueda que tiene el problema del rompecabezas,
generalmente no se busca encontrar una solución completa al mismo, en su lugar 
se intenta conseguir buenas soluciones en el sentido de maximizar la cantidad de
bordes coincidentes de una solución. Desde esta perspectiva, el problema puede
ser tratado como MAX-CSP, que, analogo a MAX-SAT busca maximizar la
cantidad de restricciones que se cumplen en una asignación.\\

Otra forma que hemos encontrado de tratar el problema es directamente
transformarlo en un problema SAT. Heule \cite{Heule} realizó un trabajo donde
propone un método de transformación de este tipo de problemas a SAT y estudia
las ventajas y desventajas, incluso a nivel del rendimiento temporal que tiene
el mismo.

\chapter{Trabajos Relacionados} 
\label{et:relacionados}
En esta sección se mencionan algunos trabajos de interés para esta tesis
relacionados con la resolución del rompecabezas EternityII. Los mismos utilizan 
técnicas basadas en metaheurísticas.\\

En el año 2009 Muñoz y col. \cite{Munoz} presentaron un trabajo donde
analizaron algunas técnicas evolutivas aplicadas a problemas del tipo satisfacción de restricciones. Utilizaron como caso de 
estudio el rompecabezas EternityII. En dicho trabajo explican tres
algoritmos evolutivos: un algoritmo genético, una implementación propia motivada en
conceptos relacionados a sistemas biológicos inmunes y un algoritmo evolutivo
multi-objetivo basado en el algoritmo genético.
Los mejores resultados los consiguieron con el algoritmo evolutivo
multi-objetivo con un valor de fitness máximo de 396 y una media de 392,5.\\

Dentro del contexto de las conferencias internacionales en metaheurísticas y computación inspirada 
en la naturaleza que se realizaron en el año 2010 \cite{Meta10} , Coelho y sus
colaboradores \cite{Coehlo} presentaron un trabajo basado en la metaheurística
Variable Neighborhood Search.
Esta metaheurística se basa en realizar una búsqueda local pero cambiando sistemáticamente el 
vecindario sobre el cual buscar, lo que permite entre otras cosas salir con
mayor facilidad de máximos locales y ampliar el espacio de búsqueda. Los resultados muestran su mejor solución con 
un score de 425, dejando correr el algoritmo un tiempo límite de una hora.\\  

Dentro de las misma conferencia, publicaron su trabajo Wei-Sin Wang y col.
\cite{WeiSin} quienes utilizaron un algoritmo Tabu Search para la resolución del problema. El algoritmo consiste básicamente 
en dos fases, la primera dedicada a resolver los bordes y esquinas del rompecabezas y la segunda 
fase dedicada a la parte interna. Ambas fases utilizan Tabu Search y en algunos casos 
Simulated Annealing para escapar de máximos locales. Tabu Search es un método que consiste en realizar 
una búsqueda local pero manteniendo una estructura de memoria de vecinos (casi
siempre una lista temporal denominada lista Tabú) que no se deben volver a visitar, al menos por un tiempo. 
Otra opción usada es que en lugar de guardar los vecinos que no se deben volver a visitar se guarden 
como tabú ciertos atributos que definen a los vecindarios. El trabajo dió como resultados soluciones 
con promedio del score cercano a 408 y como mejor solución a una con 418. Dentro de sus conclusiones 
hacen mención a la gran cantidad de locales óptimos que presenta el problema.\\

Las mejores soluciones hasta el momento, siempre dentro del uso de
metaheurísticas, pertenecen al algoritmo creado por Schaus y
su equipo en el año 2008 \cite{Schaus} con un score de 458 y al equipo de Vancroonenburg \cite{Vancroonenburg} que en el año 2010 llegaron a un score de 459, siempre sobre un total de 480. Los primeros utilizaron 
un algoritmo que combina Constraint Programming con el método Very Large Neighborhood Search y 
los segundos implementaciones basadas en hiper-heurísticas. Si bien las
instancias que utilizaron para las pruebas no parecen ser exactamente las
correspondientes al EternityII, las mismas son de características similares por lo que entendemos que las soluciones pertenecen a las mejores
encontradas hasta el momento dentro del campo de las metaheurísticas.\\

Fuera del ámbito de las metaheurísticas, la mejor solución encontrada hasta el
momento corresponde a Louis Verhaard \cite{Verhaard}, que como se mencionó
anteriormente, recibió un premio de diez mil dólares en el año 2008 por presentar una solución parcial con un score de 467. Para encontrar la
solución utilizó un algoritmo híbrido (no metaheurístico) que, según
sus palabras, no resulta de mucho interés desde un punto de vista teórico. 
El algoritmo mezcla backtracing con reinicios, una técnica 
para calcular el scoring de grupos de piezas y un método
para separar las piezas ``buenas'' de las ``malas'' en función de las veces que
las mismas pueden ser utilizadas para lograr una coincidencia de borde con otras
piezas.

